Corelab Seminar
2006-2007
Evangelos Bampas (NTUA)
Matroids and k-extendible systems
Abstract. Our objective is to characterize classes of problems for which a greedy algorithm finds solutions provably close to optimum. To that end, we introduce the notion of k-extendible systems, a natural generalization of matroids, and show that a greedy algorithm is a 1/k-factor approximation for these systems. Many seemly unrelated problems fit in our framework, e.g.: b-matching, maximum profit scheduling and maximum asymmetric TSP.
In the second half of the paper we focus on the maximum weight b-matching problem. The problem forms a 2-extendible system, so greedy gives us a 1/2-factor solution which runs in O(mlogn) time. We improve this by providing two linear time approximation algorithms for the problem: a 1/2-factor algorithm that rungs in O(bm) time, and a (\frac{2}{3} - \epsilon)-factor algorithm which runs in expected O(bm\log(\frac{1}{\epsilon})) time.
(based on work by Julián Mestre)
Material. Slides [pdf].